package JZOffer;

public class _15 {
    class Solution {
////        方法一，非递归实现
//        public ListNode Merge(ListNode list1,ListNode list2) {
//            ListNode res = new ListNode(0);
//            ListNode pos = res;
//            while(list1 != null && list2 != null) {
//                if (list1.val > list2.val) {
//                    pos.next = list2;
//                    pos = pos.next;
//                    list2 = list2.next;
//                }else {
//                    pos.next = list1;
//                    pos = pos.next;
//                    list1 = list1.next;
//                }
//            }
//            if (list1 != null) {
//                pos.next = list1;
//            }else if (list2 != null) {
//                pos.next = list2;
//            }
//            return res.next;
//        }
        public ListNode Merge(ListNode list1, ListNode list2) {
            if (list1 == null) return list2;
            if (list2 == null) return list1;
            ListNode res = null;
            if (list1.val > list2.val) {
                res = list2;
                res.next = Merge(list1,list2.next);
            }else {
                res = list1;
                res.next = Merge(list1.next,list2);
            }
            return res;
        }
    }

    Solution getSolution() {
        return new Solution();
    }

    public static void main(String args[]) {
        _15 c = new _15();
        _15.Solution s = c.getSolution();
        ListNode L1 = new ListNode(3);
        ListNode L2 = new ListNode(4);
        ListNode L3 = new ListNode(5);
        ListNode L4 = new ListNode(6);
        ListNode L5 = new ListNode(7);
        L1.next = L2;
        L2.next = L3;
        L3.next = L4;
        L4.next = L5;
        ListNode R1 = new ListNode(1);
        ListNode R2 = new ListNode(2);
        ListNode R3 = new ListNode(7);
        ListNode R4 = new ListNode(8);
        ListNode R5 = new ListNode(9);
        R1.next = R2;
        R2.next = R3;
        R3.next = R4;
        R4.next = R5;
        ListNode res = s.Merge(L1,R1);
        while (res != null) {
            System.out.println(res.val);
            res = res.next;
        }
    }
}
